﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;
using System.Threading.Tasks;

namespace DataBaseBST
{
  
    [Serializable]
    public class BST<Key,Value> where Key : IComparable<Key>
    {
        private Node root;
        private  const bool RED = true;
        private  const bool BLACK = false;

        [Serializable]
        private class Node
        {
            internal Key key;
            internal Value val;
            internal Node left, right;
            internal int N;
            internal bool color;
            public Node(Key key, Value val, int N, bool color)
            {
                this.key = key;
                this.val = val;
                this.N = N;
                this.color = color;
            }
        }

        private bool isRed(Node x)
        {
            if (x == null)
                return false;
            return x.color == RED;
        }
        public int size() { return size(root); }

        private int size(Node x)
        {
            if (x == null)
                return 0;
            else
                return x.N;
        }

        public Value get(Key key)
        {
            return get(root, key);
        }

        private Value get(Node x, Key key)
        {
            if (x == null)
                return default(Value);
            int cmp = key.CompareTo(x.key);

            if (cmp < 0)
                return get(x.left, key);
            else if (cmp > 0)
                return get(x.right, key);
            else return x.val;
        }

        public void update(Key key,Value newValue)
        {
            var node = update(root, key);
            node.val = newValue;
            
        }

        private Node update(Node x, Key key)
        {
            if (x == null)
                return null;
            int cmp = key.CompareTo(x.key);

            if (cmp < 0)
                return update(x.left, key);
            else if (cmp > 0)
                return update(x.right, key);
            else return x;
        }

        public void put(Key key, Value val)
        {
            root = put(root, key, val);
            root.color = BLACK;
        }

        private Node put(Node x, Key key, Value val)
        {
            if (x == null)
                return new Node(key, val, 1, RED);
            int cmp = key.CompareTo(x.key);

            if (cmp < 0)
                x.left = put(x.left, key, val);
            else if (cmp > 0)
                x.right = put(x.right, key, val);
            else
                x.val = val;
            if (isRed(x.right) && !isRed(x.left))
                x = rotateLeft(x);
            if (isRed(x.left) && isRed(x.left.left))
                x = rotateRight(x);
            if (isRed(x.left) && isRed(x.right))
                flipColors(x);

            x.N = size(x.left) + size(x.right) + 1;

            return x;
        }

        public void deleteMin()
        {
            if (isEmpty())
                return;

            // if both children of root are black, set root to red
            if (!isRed(root.left) && !isRed(root.right))
                root.color = RED;

            root = deleteMin(root);
            if (!isEmpty()) root.color = BLACK;
            // assert check();
        }

        // delete the key-value pair with the minimum key rooted at h
        private Node deleteMin(Node h)
        {
            if (h.left == null)
                return null;

            if (!isRed(h.left) && !isRed(h.left.left))
                h = moveRedLeft(h);

            h.left = deleteMin(h.left);
            return balance(h);
        }


        // delete the key-value pair with the maximum key
        public void deleteMax()
        {
            if (isEmpty())
                return;

            // if both children of root are black, set root to red
            if (!isRed(root.left) && !isRed(root.right))
                root.color = RED;

            root = deleteMax(root);
            if (!isEmpty()) root.color = BLACK;
            // assert check();
        }

        // delete the key-value pair with the maximum key rooted at h
        private Node deleteMax(Node h)
        {
            if (isRed(h.left))
                h = rotateRight(h);

            if (h.right == null)
                return null;

            if (!isRed(h.right) && !isRed(h.right.left))
                h = moveRedRight(h);

            h.right = deleteMax(h.right);

            return balance(h);
        }

        // delete the key-value pair with the given key
        public void delete(Key key)
        {
            if (!contains(key))
            {
                throw new Exception("Key Exists!");
                return;
            }

            // if both children of root are black, set root to red
            if (!isRed(root.left) && !isRed(root.right))
                root.color = RED;

            root = delete(root, key);
            if (!isEmpty()) root.color = BLACK;
            // assert check();
        }

        // delete the key-value pair with the given key rooted at h
        private Node delete(Node h, Key key)
        {
            // assert contains(h, key);

            if (key.CompareTo(h.key) < 0)
            {
                if (!isRed(h.left) && !isRed(h.left.left))
                    h = moveRedLeft(h);
                h.left = delete(h.left, key);
            }
            else
            {
                if (isRed(h.left))
                    h = rotateRight(h);
                if (key.CompareTo(h.key) == 0 && (h.right == null))
                    return null;
                if (!isRed(h.right) && !isRed(h.right.left))
                    h = moveRedRight(h);
                if (key.CompareTo(h.key) == 0)
                {
                    Node x = min(h.right);
                    h.key = x.key;
                    h.val = x.val;
                    // h.val = get(h.right, min(h.right).key);
                    // h.key = min(h.right).key;
                    h.right = deleteMin(h.right);
                }
                else h.right = delete(h.right, key);
            }
            return balance(h);
        }

        /*************************************************************************
         *  red-black tree helper functions
         *************************************************************************/

        // make a left-leaning link lean to the right
        private Node rotateRight(Node h)
        {
            // assert (h != null) && isRed(h.left);
            Node x = h.left;
            h.left = x.right;
            x.right = h;
            x.color = x.right.color;
            x.right.color = RED;
            x.N = h.N;
            h.N = size(h.left) + size(h.right) + 1;
            return x;
        }

        // make a right-leaning link lean to the left
        private Node rotateLeft(Node h)
        {
            // assert (h != null) && isRed(h.right);
            Node x = h.right;
            h.right = x.left;
            x.left = h;
            x.color = x.left.color;
            x.left.color = RED;
            x.N = h.N;
            h.N = size(h.left) + size(h.right) + 1;
            return x;
        }

        // flip the colors of a node and its two children
        private void flipColors(Node h)
        {
            // h must have opposite color of its two children
            // assert (h != null) && (h.left != null) && (h.right != null);
            // assert (!isRed(h) &&  isRed(h.left) &&  isRed(h.right))
            //     || (isRed(h)  && !isRed(h.left) && !isRed(h.right));
            h.color = !h.color;
            h.left.color = !h.left.color;
            h.right.color = !h.right.color;
        }

        // Assuming that h is red and both h.left and h.left.left
        // are black, make h.left or one of its children red.
        private Node moveRedLeft(Node h)
        {
            // assert (h != null);
            // assert isRed(h) && !isRed(h.left) && !isRed(h.left.left);

            flipColors(h);
            if (isRed(h.right.left))
            {
                h.right = rotateRight(h.right);
                h = rotateLeft(h);
            }
            return h;
        }

        // Assuming that h is red and both h.right and h.right.left
        // are black, make h.right or one of its children red.
        private Node moveRedRight(Node h)
        {
            // assert (h != null);
            // assert isRed(h) && !isRed(h.right) && !isRed(h.right.left);
            flipColors(h);
            if (isRed(h.left.left))
            {
                h = rotateRight(h);
            }
            return h;
        }

        // restore red-black tree invariant
        private Node balance(Node h)
        {
            // assert (h != null);

            if (isRed(h.right)) h = rotateLeft(h);
            if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
            if (isRed(h.left) && isRed(h.right)) flipColors(h);

            h.N = size(h.left) + size(h.right) + 1;
            return h;
        }

        public bool isEmpty()
        {
            return size() == 0;
        }

        public bool contains(Key key)
        {
            return get(key) != null;
        }

        public Key min()
        {
            if (isEmpty()) return default(Key);
            return min(root).key;
        }

        // the smallest key in subtree rooted at x; null if no such key
        private Node min(Node x)
        {
            // assert x != null;
            if (x.left == null) return x;
            else return min(x.left);
        }

        private Node max(Node x)
        {
            // assert x != null;
            if (x.right == null) return x;
            else return min(x.right);
        }

        public IEnumerable<KeyValuePair<Key,Value>> keys()
        {
            Queue<KeyValuePair<Key, Value>> que = new Queue<KeyValuePair<Key, Value>>();
            keys(root, que, min(root), max(root));
            return que;
        }
        private void keys(Node x, Queue<KeyValuePair<Key, Value>> queue, Node l, Node h)
        {
            
            if (x == null)
                return;
            int cmpl = l.key.CompareTo(x.key);
            int cmph = h.key.CompareTo(x.key);

            if (cmpl < 0)
                keys(x.left, queue, l, h);
            if (cmpl <= 0 && cmph >= 0)
                queue.Enqueue(new KeyValuePair<Key,Value>(x.key,x.val));
          
            if (cmph > 0)
                keys(x.right, queue, l, h);
        }

    }
}
